package com.sicheng.lc.周赛.分类.dp;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/16 9:59
 */
public class 判断一个括号字符串是否有效 {
    //https://leetcode.cn/problems/check-if-a-parentheses-string-can-be-valid/
    public boolean canBeValid(String s, String locked) {
        if (s.length() % 2 == 1 ||
                (s.charAt(0) == ')' && locked.charAt(0) == '1') ||
                (s.charAt(s.length() - 1) == '(' && locked.charAt(locked.length() - 1) == '1')
        )
            return false;
        return dp(s, locked);
    }


    // 时间 O(n^2) 数据范围n=10^5  超时
    private boolean dp(String s, String locked) {
        int p = (s.length() >> 1) + 1;
        //dp(i,j)表示 i索引位置j状态是否可以达到
        boolean[][] dp = new boolean[s.length()][p];
        dp[0][1] = true;


        for (int i = 1; i < s.length(); i++) {
            boolean res = false;
            for (int j = 0; j < p; j++) {
                int c = s.charAt(i) == '(' ? 1 : -1;
                if (j - c >= 0 && j - c < p)
                    dp[i][j] |= dp[i - 1][j - c];
                if (locked.charAt(i) == '0' && j + c >= 0 && j + c < p) {
                    dp[i][j] |= dp[i - 1][j + c];
                }
                res |= dp[i][j];
            }
            if (!res)
                return false;
        }

        return dp[s.length() - 1][0];
    }

    public static void main(String[] args) {
        判断一个括号字符串是否有效 solution = new 判断一个括号字符串是否有效();
        System.out.println(solution.canBeValid("))()))", "010100"));
    }
}
